/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package quicksort;

/**
 *
 * @author Gatscha
 */
public class Main {

    /**
     * @param args the command line arguments
     */

        static int[][] initArray (int num) {
		int[][] result = new int[2][num];
		for (int i = 0; i < num; i++)
                {
			result[0][i] = (int) (Math.random () * 100.0);
                        result[1][i] = (int) (Math.random () * 100.0);
                }
		return result;
	}

	/*
	 * Hilfsmethode: Ausgabe der Elemente eines Feldes
	 */
	static void printArray (int[] array) {
		for (int i = 0; i < array.length; i++)
			System.out.print (array[i] + " ");
		System.out.println ();
	}

	/*
	 * Hilfsmethode: Austauch zweier Feldelemente
	 */
	static void swap (int[] array, int idx1, int idx2) {
		int tmp = array[idx1];
		array[idx1] = array[idx2];
		array[idx2] = tmp;
	}


	/*
	 * Implementierung des QuickSort
	 */

	// Hilfsmethode f�r rekursives Sortieren
	static void qsort (int[] array, int le, int ri) {
		int lo = le, hi = ri;

		if (hi > lo) {
			// Pivotelement bestimmen
			int mid = array[(lo + hi) / 2];
			while (lo <= hi) {
				// Erstes Element suchen, das gr��er oder gleich dem
				// Pivotelement ist, beginnend vom linken Index
				while (lo < ri && array[lo] < mid)
					++lo;

				// Element suchen, das kleiner oder gleich dem
				// Pivotelement ist, beginnend vom rechten Index
				while (hi > le && array[hi] > mid)
					--hi;

				// Wenn Indexe nicht gekreuzt --> Inhalte vertauschen
				if (lo <= hi) {
					swap(array, lo, hi);
					++lo;
					--hi;
				}
			}
			// Linke Partition sortieren
			if (le < hi) {
				qsort (array, le, hi);
			}

			// Rechte Partition sortieren
			if (lo < ri) {
				qsort( array, lo, ri);
			}
		}
	}

	static void quickSort (int[] array) {
		qsort (array, 0, array.length - 1);
	}

	public static void main(String[] args) {
		int[][] array = null;
                array = initArray (20);
                for(int i = 0; i < 20; i++)
                {
                    System.out.print (array[0][i]+" ");
            }
                
                System.out.printf ("\n");
                for(int i = 0; i < 20; i++)
                {
                    System.out.print (array[1][i]+" ");
            }

                //Kopie anlegen
                int[][] kopie = new int[2][20];

                for(int i = 0; i < 20; i++)
                {
                    kopie[0][i] = array [0][i];
                    kopie[1][i] = array [1][i];
                }

		
                System.out.printf ("\n\n");
		quickSort (array[1]);

                for(int i = 0; i < 20; i++)
                {
                    int hilf = array[1][i];
                    int hilf2 = -1;
                    int hilf3 = 0;

                    while(hilf2 == -1)
                    {
                         if(kopie[1][hilf3] == hilf)
                         {
                            array[0][i] = kopie[0][hilf3];
                            kopie[0][hilf3] = -1;
                            kopie[1][hilf3] = -1;
                            hilf2 = hilf3;
                         }
                         hilf3++;
                    }
                }
                
		for(int i = 0; i < 20; i++)
                {
                    System.out.print (array[0][i]+" ");
                    
            }
                
                System.out.printf ("\n");
                for(int i = 0; i < 20; i++)
                {
                System.out.print (array[1][i]+" ");
	}
                }


}
